﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * There are some prime values, p, for which there exists a positive integer, n, such that the expression n^3 + n^2*p is a perfect cube.

For example, when p = 19, 8^3 + 8^2×19 = 12^3.

What is perhaps most surprising is that for each prime with this property the value of n is unique, and there are only four such primes below one-hundred.

How many primes below one million have this remarkable property?

     * */
    class Problem131 : IProblem
    {
        public string Calculate()
        {
            SieveOfAtkin sieve = new SieveOfAtkin(1000000);
            int count = 0;
            long limit = (long)Math.Pow(10, 6);

            for (long b = 1; true; b++)
            {
                long p = 3 * b * b + 3 * b + 1;

                if (sieve.IsPrime(p))
                {
                    if (p >= limit)
                        return count.ToString();

#if TRACE_1
                    Console.WriteLine("{0}^3 + {0}^2*{1} = {2}^3 : a={3}", n, p, n + a, a);
                    Console.ReadKey();
#endif
                    count++;
                }
            }
        }
    }
}
